#pragma once

#include "iostream"
#include "vector"
#include "algorithm"
#include "TypeDefin.h"
#include "queue"

using namespace std;

/*HJJ QQ479287006
 *从上到下打印出二叉树的每个节点，同一层的节点按照从左到右的顺序打印。

 

例如:
给定二叉树: [3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7
返回：

[3,9,20,15,7]

 * */

vector<int> levelOrder(TreeNode *root) {
    vector<int> ret;
    if (root == nullptr)
        return ret;


    queue<TreeNode *> q;
    q.push(root);
    while (!q.empty()) {
        TreeNode *temp = q.front();
        q.pop();
        ret.push_back(temp->val);
        if (temp->left != nullptr)
            q.push(temp->left);
        if (temp->right != nullptr)
            q.push(temp->right);

    }

    return ret;
}
//利用递归写第二题 非递归没写呢 书上的经典例题

void levelOrderII(TreeNode *root, int h, vector<vector<int>> &ret) {
    if (root == nullptr)
        return;

    if (h == ret.size()) {
        vector<int> temp;
        ret.push_back(temp);
    }

    ret[h].push_back(root->val);

    levelOrderII(root->left, h + 1, ret);
    levelOrderII(root->right, h + 1, ret);
}


void levelOrderIII(TreeNode *root, int h, vector<vector<int>> &ret) {
    if (root == nullptr)
        return;

    if (h == ret.size()) {
        vector<int> temp;
        ret.push_back(temp);
    }

    if (h % 2 != 0)
        ret[h].insert(ret[h].begin() + 0, root->val);
    else
        ret[h].push_back(root->val);

    levelOrderIII(root->left, h + 1, ret);
    levelOrderIII(root->right, h + 1, ret);
}

//第二题
vector<vector<int>> levelOrder(TreeNode *root) {
    vector<vector<int>> ret;
    levelOrderII(root, 0, ret);
    return ret;
}